COMMENT ⊗   VALID 00018 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	PAGE 21. FIGURES: PUMP VIDEO & PUMP VECTOR CONTOURS.
C00004 00003	PAGE 22. THE ALGORITHM:	INTRODUCTION.
C00006 00004	PAGE 23. FIGURES.
C00007 00005	PAGE 24. 1. THRESHOLDING.
C00010 00006	PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
C00011 00007	PAGE 26. 2. CONTOURING.
C00017 00008	PAGE 27. FIGURES: NESTING ILLUSTRATED.
C00018 00009	PAGE 28. 3. NESTING.
C00023 00010		Let the given polygon be named Poly and let the surrounder
C00025 00011	PAGE 29. NESTING ILLUSTRATED. CONTINUED.
C00026 00012	PAGE 30. NESTING CONTINUED.
C00027 00013	PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
C00028 00014	PAGE 32. 4. SMOOTHING.
C00031 00015	PAGE 33. FIGURES: COMPARING ILLUSTRATED.
C00032 00016	PAGE 34. 5. COMPARING.
C00034 00017	PAGE 35. LAMINA INERTIA TENSOR.
C00035 00018	PAGE 36. PERFORMANCE.
C00036 ENDMK
C⊗;
PAGE 21. FIGURES: PUMP VIDEO & PUMP VECTOR CONTOURS.
PAGE 22. THE ALGORITHM:	INTRODUCTION.

	CRE  consists  of  five  steps:  thresholding,    contouring,
nesting,    smoothing  and  comparing.  Thresholding, contouring  and
smoothing perform conversions between two different kinds  of images.
Nesting  and contouring  compute topological  relationships within  a
given image representation. In summary the major operations are:

	MAJOR OPERATION.	OPERAND.	  RESULT.

	1. THRESHOLDING: 	6-BIT-IMAGE,	  1-BIT-IMAGES.
	2. CONTOURING: 	 	1-BIT-IMAGES,	  VIC-IMAGE.
	3. NESTING:		VIC-IMAGE,	  NESTED-VIC-IMAGE.
	4. SMOOTHING:	 	VIC-IMAGE,	  ARC-IMAGE.
	5. COMPARING:		IMAGE & FILM,	  FILM.

	Although the natural  order of operations is  sequential from
image thresholding  to image comparing; in order  to keep memory size
down, the first four steps are applied one intensity level at  a time
from the  darkest cut to  the lightest  cut (only nesting  depends on
this  sequential cut order).  However, comparing is  applied to whole
images.

The illustrations  on pages  21 and  23 show  a video  image and  its
initial  sawtooth contours; the  illustrations immediately  below and
on page 24 illustrate the smoothed arc contours generated by CRE.


FIGURE: PUMP ARC CONTOURS.
PAGE 23. FIGURES.
DBA'S TOMBSTONE VIDEO.
DBA'S SMOOTHED CONTOURS.
PAGE 24. 1. THRESHOLDING.

	Thresholding, the  first and easiest  step,  consists  of two
subroutines,    called THRESH  and  PACXOR. THRESH  converts  a 6-bit
image into a 1-bit image with respect to a given threshold  cut level
between zero  for black and  sixty-three for light. All  pixels equal
to or  greater than the cut, map into a one; all the pixels less than
the cut, map into zero. The resulting 1-bit image is  stored in a bit
array  of  216  rows by  288  columns  (1728  words) called  the  PAC
(picture accumulator)  which  was  named  in  memory  of  McCormick's
ILLIAC-III.  After THRESH,   the PAC contains blobs of bits.   A blob
is defined as  "rook's move" simply connected; that is every bit of a
blob can be reached  by horizontal or  vertical moves from any  other
bit  without  having to  cross  a  zero bit  or  to  make a  diagonal
(bishop's) move.  Blobs may of course have holes.  Or equalvalently a
blob always  has  one  outer perimeter  polygon,  and may  have  one,
several or  no inner perimeter polygons. This  blob and hole topology
is recoverible  from the  CRE  data structure  and  is built  by  the
nesting step.

	Next,   PACXOR copies the  PAC into  two slightly larger  bit
arrays named HSEG and  VSEG. Then the PAC is shifted down one row and
exclusive OR'ed into  the HSEG array;  and the  PAC is shifted  right
one column  and exclusive OR'ed  into the  VSEG array to  compute the
horizontal and  vertical border bits of the PAC blobs.  Notice,  that
this is the very heart  of the "edge finder" of CRE. Namely,   PACXOR
is the mechanism that converts regions into edges.
PAGE 25. FIGURES. DEKINKING ILLUSTRATED.
PAGE 26. 2. CONTOURING.

	Contouring,   converts  the  bit arrays  HSEG  and VSEG  into
vectors  and polygons.  The  contouring itself,  is  done by a single
subroutine named MKPGON,  make polygon.   When MKPGON is called,   it
looks for the upper most left non-zero  bit in the VSEG array. If the
VSEG  array is empty, MKPGON returns a  NIL. However, when the bit is
found, MKPGON traces and  erases the polygonal outline to  which that
bit belongs and returns a polygon node with a ring of vectors.

	To belabor the details  (for the sake of later complexities);
the MKGON trace  can go  in four  directions: north  and south  along
vertical columns of  bits in the VSEG  array, or east and  west along
horizontal rows of  the HSEG array. The trace starts by heading south
until it hits a turn; when heading south MKPGON must check  for first
a turn  to the east (indicated  by a bit  in HSEG); next for  no turn
(continue  south); and last  for a turn  to the west. When  a turn is
encountered MKPGON  creates a  vector  node representing  the run  of
bits  between the  previous turn  and the  present turn.    The trace
always ends heading west bound.  The outline so traced can be  either
the edge  of a blob  or a  hole, the two  cases are distinguished  by
looking  at the VIC-polygon's  upper left most  pixel in  the PAC bit
array.

	There  are  two   complexities:  contrast  accumulation   and
dekinking.    The  contrast  of  a vector  is  defined  as  (QUOTIENT
(DIFFERENCE  (Sum of pixel values  on one side  of the vector)(Sum of
pixel values on the other  side ofthe vector)) (length of  the vector
in pixels)).  Since  vectors are always either horizontal or vertical
and are construed  as being on  the cracks between  pixels; thus  the
specified summations refer  to the pixels immediatelt to  either side
of the  vector. Notice that this definition  of constrast will always
give  a positive  constrast  for  vectors  of  a  blob  and  negative
contrast for the vectors of a hole.

	The terms "jaggies",  "kinks"  and "sawtooth" all are used to
express  what seems to be  wrong about the  uppermost left polygon on
page 25.    The problem  involves doing  something  to a  rectilinear
quantized set of  segments,  to make its  linear nature more evident.
The CRE jaggies solution (in the subroutine MKPGON) merely  positions
the  turning locus  diagonally  off its  grid  point alittle  in  the
direction  (northeast,    northwest,   southwest  or  southeast) that
bisects the  turn's  right  angle.  The distance  of  dekink  vernier
positioning  is  always less  than  half  a  pixel; but  greater  for
brighter cuts  and less for the darker cuts; in order to preserve the
nesting of contours. 
PAGE 27. FIGURES: NESTING ILLUSTRATED.
1ST FRAME FLAT NEST.
2ND FRAME GEOMED NEST.

PAGE 28. 3. NESTING.

	The nesting problem is to decide  whether one contour polygon
is  within another.  Although  easy in the two  polygon case; solving
the nesting  of many  polygons  with respect  to each  other  becomes
n-squared expensive in  either compute time or in memory  space.  The
nesting  solution in CRE  sacrifices memory for speed  and requires a
31K array, called the SKY.

	CRE's accumulation  of  a properly  nested  tree of  polygons
depends on the  order of threshold cutting going  from dark to light.
For each polygon there are two  nesting steps: first, the polygon  is
placed in  the  tree of  nested polygons  by  the subroutine  INTREE;
second,   the polygon  is placed in  the SKY array  by the subroutine
named INSKY.

	The SKY array is 216 rows of 288 columns of  18-bit pointers.
The name "SKY"  came about because,  the array  used to represent the
furthest  away regions or  background, which  in the case  of a robot
vehicle is the real sky  blue. The sky contains vector  pointers; and
would be  very efficient on on  a virtual memory  machine that didn't
allocate unused pages of its  address space.  Whereas most  computers
have more  memory containers  than address  space; computer  graphics
and vision  might be easier to program in  a memory with more address
space than physical space; i.e. an almost empty virtual memory.

	The first part of the INTREE routine  finds the surrounder of
a given polygon  by scanning the SKY due east from the uppermost left
pixel of  the given polygon.   The  SON of  a polygon  is always  its
uppermost  left  vector. After  INTREE,    the INSKY  routine  places
pointers  to the vertical vectors  of the given  polygon into the sky
array.

	The second part  of the INTREE  routine checks for and  fixes
up the case where the  new polygon captures a polygon that is already
enclaved. This only  happens when  two or  more levels  of the  image
have blobs that have holes.   The rest of this section  is devoted to
the  arcane details of  fixing up the  tree link of  multi level hole
polygons.

	Let the given polygon be named Poly; and let the surrounder
of Poly be called Exopoly; and assume that Exopoly surrounds a
a several hole polygon
named Hole1, Hole2, etc.; which are already in the nested polygon tree.
That is Hole1 is the ENDO of Exopoly's; and is one of a ring of holes called
the ENDO ring of Exopoly.
Now the subrotine INTREE must re-scan the sky array 
for the EXO's of all the polygons  on
Exopoly's ENDO ring.

On such rescanning there are  four cases:
	1. No change:	the scan returns Exopoly; which is the hole's
	   original EXO.
	2. Poly captures Hole; the scan returns Poly indicating
	   the Endo has been captured by POLY;
	3. My brothers fate; the ENDO hits an endo which
	   is not on the P-list.
	4. My fate delayed;

	Since deep holes frequently occur in natural images, (even in
images of pears and apples) I was amused to see that not a single deep
hole occurs in the examples in Krakauer's thesis which was about
nested polygon trees of video intensity contours.
PAGE 29. NESTING ILLUSTRATED. CONTINUED.
PAGE 30. NESTING CONTINUED.
PAGE 31. FIGURES: RECURSIVE SMOOTHING ILLUSTRATED.
PAGE 32. 4. SMOOTHING.

	In CRE the term  "smoothing" refers more  to the
problem  of breaking a  manifold up  into functions, rather  than to the
problem of fitting functions to measured data.

	The smoothing step in CRE, converts the polygons  of vertical
and horizontal  vectors into  polygons of arcs.  For the  present the
term "arc"  means "linear arc" which is a line segment. Fancier arcs:
circular and cubic spline  were tried and found expensive  to compute
and unwieldly  to manipulate; however  fancy arcs were  doomed by the
fact that  after  going  to  all  the  trouble  of  implementing  and
computing them, there remained the overpowering  demand to break them
down again  into linear vectors for  computing areas, inertia tensors
or mere display buffers.

	To start, a ring  of two arcs is  formed (a bi-gon) with  one
arc at  the uppermost left  and the other  at the lowermost  right of
the  given  polygon  of  vectors.  Now  the  smoothing  operation  is
recursive; each arc  is in one  to one correspondece  with a list  of
vectors; if each point on  the list of vectors is close enough to the
approximating arc than  MKARC returns  the given arc  as goo  enough;
otherwise MKARC split  the arc in two and  place a new arc  vertex on
the vector vertex tht was furthest away from the original arc.

	This  manner of  smooth collaspes  the  stair cases  of jaggy
quantum edges.

PAGE 33. FIGURES: COMPARING ILLUSTRATED.

1ST Q3
2ND Q4
3RD FUSION Q3 AND Q4
4TH BABY.

PAGE 34. 5. COMPARING.

	The compare step of CRE connects the polygons and
arcs of the current image with corresponding polygons and arc
of the previous image. CMPARE solves the problem of correlating
features between two similar images.

CMPARE is composed of four sections: 

	1. make shape nodes for polygons.
	2. compare and connect polygons one to one.
	3. compare and connect polygons two to one.
	4. compare and connect vertices of two polygons.

	First the shape nodes for
all the polygons of the current image are computed; second, the
polygons of each level of the current image are compared with
the corresponding level of the previous image for one to one match;
third, the unmated polygons of the current level aree compared with.
PAGE 35. LAMINA INERTIA TENSOR.
PAGE 36. PERFORMANCE.